\documentclass[10pt, a4paper, spanish, notitlepage]{article}
 
\usepackage[spanish]{babel} 
\usepackage[utf8]{inputenc}
\usepackage{pepotina} %paquete personal para mi pepotina
\usepackage{graphicx}
\usepackage{fancyhdr} %linea sup con comentarios
\usepackage{lastpage} %ultima pagina
\usepackage{color}
\usepackage{listings}
\usepackage{courier}

\definecolor{gray97}{gray}{.97}
\definecolor{gray55}{gray}{.55}
\definecolor{gray30}{gray}{.30}

\lstset{
	language=C++,
	frame=single,
	framerule=0.1pt, 
	backgroundcolor=\color{gray97},
	aboveskip=8pt,
	belowskip=12pt,
	commentstyle=\color{gray55},
	basicstyle=\small\ttfamily, 
	keywordstyle=\bfseries,
	stringstyle=\color{gray30},
	framextopmargin=4pt,
	framexbottommargin=4pt,
	framexleftmargin=4pt,
	framexrightmargin=4pt,
	breaklines=true,
	showstringspaces=false,
	abovecaptionskip=-3pt,
	tabsize=4
}

\addtolength{\topmargin}{-50pt} 
\addtolength{\textwidth}{105pt}
\addtolength{\textheight}{120pt}
\addtolength{\oddsidemargin}{-50pt}
\headheight 15.0pt

\setlength{\tabcolsep}{10pt}
\renewcommand{\arraystretch}{1.5}
\parskip 5pt

\pagestyle{fancy}
\fancyhead[LO]{Teoría de Lenguajes - Trabajo Práctico - 2º cuatrimestre 2011}
\fancyhead[C]{}
\fancyhead[RO]{Página \thepage\ de \pageref{LastPage}}
\renewcommand{\headrulewidth}{0.4pt}
\fancyfoot[LO]{}
\fancyfoot[C]{}
\fancyfoot[RO]{Juan Manuel Pérez, Sebastián Tleye y Gabriel Finkelstein}
\renewcommand{\footrulewidth}{0.4pt}

\begin{document} 
\titulo{Trabajo Práctico}
\materia{Teoría de Lenguajes}
\integrante{Juan Manuel Pérez}{jmperez85@gmail.com}
\integrante{Sebastián Tleye}{stleye@gmail.com}
\integrante{Gabriel Finkelstein}{gabrielfinkelstein@gmail.com}
\universidad{Universidad de Buenos Aires}
\facultad{Facultad de Ciencias Exactas y Naturales}
\departamento{Departamento de Computación}
\fecha{Segundo cuatrimestre de 2011}
\footspace{2cm}
\parskip 7.2pt
\maketitle

\newpage

\tableofcontents

\newpage

\section{Gramática y generador elegido}
Para implementar el trabajo práctico utilizamos el lenguaje C++, en conjunto con el generador de parsers Bison.

Bison reconoce gramáticas LALR. Ésto nos da una gran ventaja (por ejemplo, a comparación de ANTLR, que sólo reconoce LL) ya que podemos reconocer el lenguaje haciendo modificaciones mínimas, o ni siquiera ésto.

Como puede verse, la gramática que fue dada por la cátedra contiene ambiguedades. Por consiguiente, necesariamente tendrá conflictos LALR. Ante ésto, podemos hacer dos cosas:

\begin{itemize}
	\item Modificar la gramática para que no contenga errores LALR.
	\item Resolver los conflictos LALR mediante la precedencia de sus operadores.
\end{itemize}

Decidimos tomar el camino de la segunda opción, ya que ésto nos permite seguir utilizando una gramática más clara (una razón por la que a veces conviene utilizar gramátias ambiguas). También pudimos explorar la forma de resolver conflictos LALR utilizando Bison. 

Si hubiésemos decidido utilizar un generador LL tendríamos que haber modificado la gramática para eliminar estos conflictos, obteniendo una gramática mucho más intrincada.

\section{Resolución de conflictos}

\subsection{Precedencia de \texttt{`|'}, concatenación y operadores unarios}

Es necesario indicar en el archivo de entrada de Bison la precedencia de los distintos operadores del lenguaje, y también la de los tokens, para resolver los conflictos S/R, o R/R que surjan. Ésto se puede hacer definiendo conjuntos de tokens ubicados en lineas separadas según el orden de precedencia. Por ejemplo, para decir que los operadores unarios tienen mayor precedencia que el operador \texttt{`|'}  escribimos lo siguiente:

\begin{lstlisting}[]
%left '|'
%nonassoc '+' '*' '?'
\end{lstlisting}

Donde \texttt{\%left} indica que el operador es asociativo a izquierda, \texttt{\%right} a derecha, y \texttt{\%nonassoc} que no tiene asociatividad. Cuanto más arriba aparezca un conjunto de tokens, menor precedencia tiene.

Con las reglas indicadas logramos que, por ejemplo, en la expresión $a|b+$ cuando surja un conflicto de $reduce$ por $E \rightarrow E|E$ / $shift$ por $+$, primero hará $shift$ y luego el $reduce$. \\

Para indicar la precedencia de la concatenación surge un problema, ya que al ser el operador implícito no existe un token al cual definirsela. Sin embargo, sí es posible asignarle precedencia a una producción. Para ello se agrega al final de ésta la palabra clave \texttt{\%prec} seguida de un token o un literal. Esto hace que la producción tenga la precedencia de este token o literal.

Entonces, en el caso de la concatenación agregamos:

\begin{lstlisting}[]
%left '|'
%left CONCAT
%nonassoc '+' '*' '?'
\end{lstlisting}
 
 Y luego:
 
\begin{lstlisting}[]
exp: exp exp	%prec CONCAT
\end{lstlisting}

Como shiftear un caracter tiene más precedencia que efectuar la reducción por disyunción, pero menos que la reducción por concatenación, agregamos:

\begin{lstlisting}[]

%left '|'
%nonassoc CARACTER '.'
%left CONCAT 
%nonassoc '+' '*' '?'
...
exp : CARACTER 
\end{lstlisting}

En este caso estamos dandole precedencia directamente al token caracter.

Reducir un paréntesis SIEMPRE tiene más precedencia que cualquier otra acción. Agreguemos ésto con la mayor precedencia

\begin{lstlisting}[]

%left '|'
%nonassoc CARACTER '.'
%left CONCAT 
%nonassoc '+' '*' '?'
%nonassoc PARENTESIS
...

exp : (exp) %prec PARENTESIS
\end{lstlisting}

Ahora, ¿cuándo shifteamos un $($?. Si tenemos una reducción por multiplicación en el stack, y un $($ en el lookahead, deberíamos reducir (es decir, $CONCAT$ tendría más precedencia que el $($). Ahora, si tengo una reducción por disyunción, y el lookahead es un $($, debería shiftear, ya que eso necesariamente es una multiplicación!.

La precedencia definitiva de caracteres y operadores es:

\begin{lstlisting}[]
%left '|'
%nonassoc CARACTER '.'
%nonassoc '('
%left CONCAT 
%nonassoc '+' '*' '?'
%nonassoc PARENTESIS

\end{lstlisting}

Obviamente la precedencia entre caracteres no es importante, ya que nunca hay conflictos Shift-Shift ;).
\newpage
\section{Generación de un AFND a partir de la gramática}

En el archivo de entrada de Bison debemos asignarle a cada producción de la gramática un código en C++ que se ejecutará cada vez que se utilice la producción correspondiente durante el parseo. En nuestro caso, queremos asociar cada operación entre una o más partes de una expresión regular con una operación entre uno o más autómatas finitos no determinísticos.
A continuación mostramos la relación entre cada producción, y el autómata asociado a ésta.

\subsection{$E \rightarrow R | S$}

\noindent \includegraphics[scale=0.4]{imagenes/automata1.png}

\subsection{$E \rightarrow R S$}

\noindent \includegraphics[scale=0.4]{imagenes/automata2.png}

\subsection{$E \rightarrow R*$}

\noindent \includegraphics[scale=0.4]{imagenes/automata3.png}

\subsection{$E \rightarrow R+$}

\noindent \includegraphics[scale=0.4]{imagenes/automata4.png}

\subsection{$E \rightarrow R?$}

\noindent \includegraphics[scale=0.4]{imagenes/automata5.png}

\subsection{$E \rightarrow caracter$ y $E \rightarrow .$}

\noindent \includegraphics[scale=0.6]{imagenes/automata6.png}

\section{Información para compilar y correr el proyecto}

Para compilar el proyecto, utilizamos bison 2.4.1, en conjunción con flex 2.5.35, g++ 4.4.5, y la herramienta make. Es necesario tener instaladas las librerías TR1 de C++.

Para compilar el proyecto, basta pararse en el raíz 


\begin{lstlisting}[language=C,title=$$]
jmperez@ws13lab05:~/tp-tlen$ make
g++ -g -c -o Automatas.o Automatas.cpp
g++ -g -c -o NFAtoDFA.o NFAtoDFA.cpp
g++ -g -o automata_tests Automatas.o automata_tests.cpp NFAtoDFA.o
bison -d -v exp.y
flex --header-file=lex.yy.h exp.l
g++ -g -c lex.yy.c 
g++ -g NFAtoDFA.o Automatas.o lex.yy.c exp.tab.c -o exp -lfl
jmperez@ws13lab05:~/tp-tlen$

\end{lstlisting}

El ejecutable generado tiene por nombre exp. Para correrlo, hay que llamarlo con dos parámetros: la expresión regular, y el archivo sobre el cuál se va a realizar la búsqueda.

Por ejemplo:

\begin{lstlisting}[language=C,title=$$]
jmperez@ws13lab05:~/tp-tlen$ ./exp ".*comp(utacion)(pepe)?.*" Tests/test5
ciencias de la computacion
ciencias de la computacion 1
me gusta ciencias de la computacion y ciencias matematicas
jmperez@ws13lab05:~/tp-tlen$
\end{lstlisting}
\newpage

\section{Casos de prueba}

Para probar el programa, escribimos 5 archivos con palabras, y expresiones regulares varias que aceptaban algunas de ellas.

Estos archivos se encuentran en el directorio Tests del raíz del TP. En la primer línea se encuentran, separadas por espacios, expresiones regulares a utilizar en dichos archivos.


\subsection{Caso 1}

Probamos la precedencia de la concatenación por sobre el operador $|$, pero no el operador $+$.

\begin{lstlisting}[title=Tests/test6]
acccc
bcccc
a
bcbcbc
\end{lstlisting}

\begin{lstlisting}[title=Salida con $a|bc+$]
$ ./exp "a|bc+" Tests/test6
bcccc
a
\end{lstlisting}

Probamos que sucede con las precedencias al utilizar paréntesis.

\begin{lstlisting}[title=Salida con $(a|b)c+$]
$ ./exp "(a|b)c+" Tests/test6
acccc
bcccc
\end{lstlisting}

\begin{lstlisting}[title=Salida con $a|(bc)+$]
$ ./exp "a|(bc)+" Tests/test6
a
bcbcbc
\end{lstlisting}

\begin{lstlisting}[title=Salida con $a|(bc+$]
$ ./exp "a|(bc+" Tests/test6
ERROR(PARSER): syntax error, unexpected $end
\end{lstlisting}

\subsection{Caso 2}

Probemos la precedencia de los operadores de concatenación y $|$. Utilizamos como expresión regular a $(1|0)*0001$, es decir, todas las cadenas que terminen en $0001$. Como entrada, utilizaremos test4.

\begin{lstlisting}[title=Tests/test4]
0101010101011000011010111000000000010001
1111111111000000000000000000001111110001
0000000000000000000000000000000000000001
1111111111111111111111111111111111111111
0000000000000000000000000000000000000000
\end{lstlisting}

\begin{lstlisting}[title=Salida con $(1|0)*0001$]
$ ./exp "(1|0)*0001" Tests/test4
0101010101011000011010111000000000010001
1111111111000000000000000000001111110001
0000000000000000000000000000000000000001
\end{lstlisting}

\subsection{Caso 3} 


Probaremos la precedencia de la concatenación sobre los paréntesis, mezclando operadores binarios. Para éso, utilizamos como expresión regular $.*comp(utacion)(pepe)?.*$



\begin{lstlisting}[title=Tests/test5]
ciencias de la computacion
CIENCIAS DE LA COMPUTACION
ciencias matematicas
ciencias de la computacion 1
me gusta ciencias de la computacion y ciencias matematicas
\end{lstlisting}

\begin{lstlisting}[title=Salida con $.*comp(utacion)(pepe)?.*$]
$ ./exp ".*comp(utacion)(pepe)?.*" Tests/test5
ciencias de la computacion
ciencias de la computacion 1
me gusta ciencias de la computacion y ciencias matematicas
\end{lstlisting}

\section{Conclusiones}

Por un lado, la posibilidad de resolver los conflictos de la gramática sin modificarla, nos ha dado una capacidad expresiva muy grande, y escribir la TDS para calcular el autómata no determinístico ha sido muy simple a raíz de ésto.

Ésto nos demuestra qué tan importante es poder trabajar con gramáticas ambiguas.

Por otro lado, la construcción de un DFA y un NFA nos insumió una gran cantidad de tiempo. La complejidad asintótica del algoritmo de conversión de NFA a DFA puede sin duda bajarse haciendo cálculos más inteligentes y eligiendo mejores estructuras de datos, pero el tiempo nos apremió y no pudimos hacerlo.



\section{Código fuente}

\subsection{Archivo lex}
\lstset{title=exp.l}
\lstinputlisting{../exp.l}

\subsection{Archivo yacc}
\lstset{title=exp.y}
\lstinputlisting{../exp.y}

\subsection{Clases para autómatas}
\lstset{title=Automatas.cpp}
\lstinputlisting{../Automatas.cpp}

\subsection{Conversión de AFND a AFD}
\lstset{title=NFAtoDFA.cpp}
\lstinputlisting{../NFAtoDFA.cpp}


\end{document}
